package j2024.j202410;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class j1021 {
    /**
     *
     * 30. 串联所有单词的子串
     * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
     *
     *  s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
     *
     * 例如，如果 words = ["ab","cd","ef"]，
     * 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
     * "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
     * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
        HashMap<String,Integer> map = new HashMap<>();
        for(String word:words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        int m = words.length;
        int n = words[0].length();
        List<Integer> ret = new ArrayList<>();
        //把words中的单词看成一个字母
        //一个单词长度作为循环次数
        for (int i = 0; i < n; i++) {
            HashMap<String,Integer> tmp = new HashMap<>();
            for (int left = i,right = i,count = 0; right+n <= s.length(); right+=n) {
                String in = s.substring(right,right+n);
                tmp.put(in,tmp.getOrDefault(in,0)+1);
                if(tmp.get(in)<=map.getOrDefault(in,0)){
                    count++;
                }
                if(right-left+1>n*m){
                    String out = s.substring(left,left+n);
                    if(tmp.get(out)<=map.getOrDefault(out,0)){
                        count--;
                    }
                    tmp.put(out,tmp.get(out)-1);
                    left+=n;
                }
                if(count==m){
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}
